WEBVTT 00:00:01.000 --> 00:00:04.166 Y gracias a los organizadores por invitarme. 00:00:04.166 --> 00:00:04.866 hablar aquí. 00:00:05.300 --> 00:00:08.500 Me siento honrado y conmovido de hablar entre mis 00:00:08.500 --> 00:00:13.666 comunidad y hablar junto a personas cuyas obras 00:00:13.666 --> 00:00:15.800 He estado siguiendo desde el principio de mi 00:00:15.800 --> 00:00:16.466 trayectoria académica. 00:00:16.666 --> 00:00:18.500 Así que, sinceramente, muchas gracias. 00:00:19.900 --> 00:00:22.300 Así que hoy quería hablar sobre algunos 00:00:22.300 --> 00:00:24.933 trabajo que he estado haciendo sobre la preservación de la distancia 00:00:24.933 --> 00:00:26.400 aprendizaje automático de gráficos. 00:00:27.000 --> 00:00:28.966 Y antes de empezar, permítanme simplemente dar 00:00:28.966 --> 00:00:31.166 te daré una imagen que de alguna manera te motivará. 00:00:31.166 --> 00:00:32.733 el trabajo que estábamos haciendo aquí. 00:00:33.500 --> 00:00:36.233 Entonces, la idea que estábamos explorando es 00:00:36.233 --> 00:00:40.566 que los gráficos tienen topología estructural en todas las escalas. 00:00:41.200 --> 00:00:43.266 Así que puedes pensar al nivel más simple, 00:00:43.333 --> 00:00:45.400 a escala local, tienes cosas como 00:00:45.400 --> 00:00:49.266 invariancia local, pocos vecindarios de saltos, incluso muy pequeños 00:00:49.266 --> 00:00:51.800 cosas como escalares por nodo, como el grado 00:00:51.800 --> 00:00:52.966 de cada nodo. 00:00:53.600 --> 00:01:00.200 Y estas invariantes fundamentales impulsan cosas como 00:01:00.200 --> 00:01:01.300 consenso descentralizado. 00:01:01.600 --> 00:01:03.600 Impulsan cosas como las redes neuronales convolucionales de paso de mensajes. 00:01:03.600 --> 00:01:07.500 redes mediante la realización de estas agregaciones locales sucesivas. 00:01:08.333 --> 00:01:09.500 Luego, si vas al otro extremo 00:01:09.500 --> 00:01:11.366 del espectro, tienes la escala global. 00:01:11.966 --> 00:01:14.300 Y puedes pensar, cuando digo 00:01:14.300 --> 00:01:16.400 escala global aquí, estoy pensando en, tengo 00:01:16.400 --> 00:01:17.633 dos nodos en mi gráfico. 00:01:17.733 --> 00:01:18.933 No necesariamente están relacionados. 00:01:19.533 --> 00:01:21.966 ¿Cómo se relacionan a lo largo del gráfico? 00:01:21.966 --> 00:01:23.900 Entonces, por ejemplo, ¿cuántos caminos hay? 00:01:23.900 --> 00:01:24.600 ¿Entre ellos? 00:01:25.100 --> 00:01:27.433 O quizás más importante, ¿cuál es el más corto? 00:01:27.433 --> 00:01:29.166 camino que puedo tomar para llegar desde 00:01:29.166 --> 00:01:30.466 ¿De un nodo a otro nodo? 00:01:30.966 --> 00:01:32.900 Y este es un problema importante que impulsa 00:01:32.900 --> 00:01:39.466 cosas como recuperación, enrutamiento, navegación, que son muy 00:01:39.466 --> 00:01:42.166 problemas importantes en áreas como la robótica y las operaciones 00:01:42.166 --> 00:01:42.666 investigación. 00:01:43.533 --> 00:01:45.666 Y luego, en algún punto intermedio, tienes 00:01:45.666 --> 00:01:48.566 la escala mesoscópica, que es algo así como 00:01:48.566 --> 00:01:50.733 esta escala intermedia entre lo local y lo global. 00:01:51.366 --> 00:01:57.200 Y esta escala suele revelarse en las cosas 00:01:57.200 --> 00:02:00.966 como caminatas de varios saltos, resistencia efectiva, como Antonio 00:02:00.966 --> 00:02:04.566 Ortega lo dijo en la primera sesión plenaria. 00:02:05.100 --> 00:02:09.733 Y esto revelará motivos, cosas como comunidades, 00:02:10.900 --> 00:02:12.300 cuellos de botella, y así sucesivamente. 00:02:12.566 --> 00:02:14.066 Entonces, la forma en que pienso en esto es, 00:02:14.966 --> 00:02:17.866 Si sé que dos nodos están conectados 00:02:17.866 --> 00:02:20.866 por un borde, están como en 00:02:20.866 --> 00:02:22.166 esta escala local en conjunto. 00:02:22.833 --> 00:02:24.400 Si no están conectados por una arista, si 00:02:24.400 --> 00:02:25.700 Me pregunto, de acuerdo, ¿están en el? 00:02:25.700 --> 00:02:26.300 ¿La misma comunidad? 00:02:26.566 --> 00:02:28.066 Es algo así como la escala mesoscópica. 00:02:28.433 --> 00:02:29.700 Imagina que no pertenecen a la misma comunidad. 00:02:30.233 --> 00:02:31.066 ¿A qué distancia están? 00:02:31.400 --> 00:02:32.633 Y esto es lo que pienso como 00:02:32.633 --> 00:02:33.866 a escala global. 00:02:34.000 --> 00:02:37.900 Así que esta es solo una taxonomía para lo que 00:02:37.900 --> 00:02:40.400 Me refiero a cuando me refiero a estos diferentes 00:02:40.400 --> 00:02:40.733 balanza. 00:02:42.566 --> 00:02:44.933 Y luego la pregunta que nos interesaba 00:02:44.933 --> 00:02:47.766 con mi estudiante de doctorado, Milet, por la 00:02:47.766 --> 00:02:48.833 De alguna manera, debería haber dicho, esto está en 00:02:48.833 --> 00:02:52.366 colaboración con Shovik Dara de Georgia Tech y 00:02:52.366 --> 00:02:54.233 Meher Chaitanya de KTH. 00:02:55.700 --> 00:02:59.366 Entonces, lo que nos interesaba entender era: 00:02:59.866 --> 00:03:03.866 ¿Pueden los métodos de aprendizaje automático de procesamiento de señales gráficas existentes 00:03:03.866 --> 00:03:05.533 ¿Es posible integrar esta topología en todas las escalas? 00:03:06.266 --> 00:03:08.966 Entonces, cuando se trata de incrustaciones locales, GNN, 00:03:09.066 --> 00:03:10.800 Procesamiento de señales, lo hacen de maravilla. 00:03:11.066 --> 00:03:14.100 Esto lo maneja magníficamente el gráfico SP y 00:03:14.100 --> 00:03:16.233 NML, al menos en su forma tradicional. 00:03:16.866 --> 00:03:19.400 La mayoría de las redes de señales gráficas son locales. 00:03:19.933 --> 00:03:23.600 Así pues, las convoluciones se definen mediante estas sumas ponderadas. 00:03:23.600 --> 00:03:25.500 de agregaciones locales. 00:03:25.666 --> 00:03:27.200 Y esto también ocurre con la agregación. 00:03:27.200 --> 00:03:28.900 redes de paso de mensajes. 00:03:29.100 --> 00:03:30.933 Todos estos son solo nombres diferentes para el 00:03:30.933 --> 00:03:31.366 Lo mismo. 00:03:32.066 --> 00:03:34.666 Así que esto, supongo que podemos decirlo con seguridad. 00:03:35.066 --> 00:03:37.800 Esto lo gestiona en particular nuestra comunidad aquí. 00:03:39.066 --> 00:03:42.333 Pero cuando se trata del ámbito global y 00:03:42.333 --> 00:03:44.533 A escala mesoscópica, existen algunos desafíos. 00:03:44.966 --> 00:03:48.166 Por ejemplo, cuando se trata de encontrar 00:03:48.166 --> 00:03:51.400 incrustaciones globales, por ejemplo, distancias de ruta más corta entre 00:03:51.400 --> 00:03:54.900 dos nodos en un grafo, esto es difícil 00:03:54.900 --> 00:03:57.633 para manejar arquitecturas locales como las GNN. 00:03:57.766 --> 00:04:00.033 Tendrías que sentir la cantidad de 00:04:00.033 --> 00:04:03.500 lúpulo igual al diámetro, que suele ser 00:04:03.500 --> 00:04:04.600 No es algo que quieras. 00:04:05.900 --> 00:04:07.800 En teoría, esto se puede manejar mediante un grafo. 00:04:07.800 --> 00:04:11.300 transformadores, en particular densos, los llamados grafos densos 00:04:11.300 --> 00:04:13.766 transformadores, que son aquellos que permiten cada nodo 00:04:13.766 --> 00:04:16.333 atender a todos los demás nodos, incluso sin 00:04:16.333 --> 00:04:16.900 una ventaja. 00:04:18.366 --> 00:04:20.566 Sin embargo, sabemos que esto no es muy 00:04:20.566 --> 00:04:24.266 eficiente porque esta atención densa se escala como O 00:04:24.266 --> 00:04:24.800 de N al cuadrado. 00:04:25.200 --> 00:04:26.766 Tienes que llenar este denso y por 00:04:26.766 --> 00:04:27.300 matriz final. 00:04:28.200 --> 00:04:30.733 Y en particular, al pensar en el más corto 00:04:30.733 --> 00:04:32.366 problema de ruta, que es lo que vamos a ser 00:04:32.366 --> 00:04:34.766 Hablando de ello en un segundo, si estuvieras 00:04:34.766 --> 00:04:36.766 para almacenar todas las distancias más cortas desde un 00:04:36.766 --> 00:04:39.133 nodo a todos los demás nodos en el 00:04:39.133 --> 00:04:41.166 gráfico, que requiere incrustaciones n-dimensionales. 00:04:41.866 --> 00:04:45.800 Y por lo tanto no puedes, por ejemplo, transferir esto 00:04:45.800 --> 00:04:47.033 arquitectura a un gráfico más grande. 00:04:47.100 --> 00:04:48.400 No tienes ninguna generalización sobre el tamaño. 00:04:49.100 --> 00:04:51.866 Y además, quiero decir, podrías decir, está bien, 00:04:51.933 --> 00:04:54.600 No quiero encontrar todas las distancias de los caminos más cortos. 00:04:54.900 --> 00:04:57.066 Quiero encontrar la K superior, pero la 00:04:57.066 --> 00:04:58.900 Los K no coincidirán entre los nodos. 00:04:59.266 --> 00:05:02.066 Entonces tendrás este problema de los diferentes 00:05:02.066 --> 00:05:05.933 Las dimensiones de incrustación corresponderán a diferentes nodos, 00:05:06.100 --> 00:05:08.366 Y eso es muy malo para las GNN. 00:05:08.433 --> 00:05:10.133 Esto perjudica enormemente la generalización. 00:05:10.666 --> 00:05:14.666 Bien, entonces esta es un área donde ambos 00:05:14.666 --> 00:05:16.900 Las GNN y los transformadores tienen dificultades. 00:05:17.400 --> 00:05:22.100 Cuando se trata de incrustaciones mesoscópicas, la extracción de estas 00:05:22.100 --> 00:05:25.466 Incrustaciones mesoscópicas, extrayendo esto mesoscópico, ¿verdad? 00:05:25.533 --> 00:05:26.833 Entonces sabemos que, por ejemplo, si usted 00:05:26.833 --> 00:05:28.666 tienen gráficos bien comportados, como gráficos densos, 00:05:28.666 --> 00:05:32.566 Se pueden extraer cosas como comunidades mediante el uso de espectro 00:05:32.566 --> 00:05:37.400 filtros, GNN espectrales, de los cuales los filtros convolucionales y 00:05:37.400 --> 00:05:39.233 Las GNN son un tipo, ¿verdad? 00:05:39.866 --> 00:05:42.200 Pero pueden ser difíciles de aprender y 00:05:42.200 --> 00:05:43.766 práctica en algunos entornos. 00:05:44.366 --> 00:05:48.166 Y por ejemplo, tengo, es un poco 00:05:48.166 --> 00:05:50.133 un poco pequeño, pero la segunda referencia allí en 00:05:50.133 --> 00:05:51.700 La diapositiva es un documento que escribimos. 00:05:51.700 --> 00:05:54.366 hace unos años para ICASP, donde nosotros 00:05:54.366 --> 00:05:57.533 demostraron que las GNN son un poco mejores 00:05:57.533 --> 00:06:00.566 que las incrustaciones espectrales para encontrar comunidades en espacios dispersos 00:06:00.566 --> 00:06:04.533 gráficos, porque esencialmente, en gráficos dispersos, como 00:06:04.533 --> 00:06:08.966 Los K autovectores superiores no son tan informativos. 00:06:08.966 --> 00:06:10.300 ¿Como en los grafos densos, verdad? 00:06:10.600 --> 00:06:12.666 Pero lo que hacen bien las GNN es interpolar. 00:06:12.666 --> 00:06:14.800 el ruido proveniente de los otros vectores propios. 00:06:15.400 --> 00:06:16.866 Sin embargo, el problema es que cuando quieres 00:06:16.866 --> 00:06:18.966 transferir esa GNN a otros gráficos, incluso en 00:06:18.966 --> 00:06:23.466 la misma clase de familia de grafos aleatorios, este 00:06:23.466 --> 00:06:25.666 La interpolación de ruido no es muy transferible. 00:06:25.933 --> 00:06:28.100 Y entonces tienes algunos desafíos, ¿verdad? 00:06:28.133 --> 00:06:30.300 Aunque esto es factible, necesitas grandes cantidades. 00:06:30.300 --> 00:06:33.400 campo receptivo suficiente, y hay algunos desafíos 00:06:33.400 --> 00:06:36.466 asociado, por ejemplo, con grafos dispersos. 00:06:36.466 --> 00:06:39.766 La idea aquí era intentar, en 00:06:39.766 --> 00:06:43.566 Para tratar de abordar estos problemas, fue 00:06:43.566 --> 00:06:46.066 tratar de preservar la métrica adecuada para 00:06:46.066 --> 00:06:47.266 cada escala, ¿verdad? 00:06:47.366 --> 00:06:50.866 Entonces, cuando hablas de escala global, yo tengo 00:06:50.866 --> 00:06:52.866 He estado hablando mucho sobre las distancias entre nodos, 00:06:52.933 --> 00:06:53.100 ¿bien? 00:06:53.800 --> 00:06:56.000 Y en particular, la distancia del camino más corto es 00:06:56.000 --> 00:06:57.300 Una métrica válida, ¿verdad? 00:06:57.366 --> 00:07:00.500 Entonces lo que haremos aquí es yo 00:07:00.500 --> 00:07:04.266 te mostrará esta clase de algoritmos que 00:07:04.266 --> 00:07:06.433 Creo que se ha estudiado durante un buen tiempo. 00:07:06.433 --> 00:07:09.966 mientras que, y especialmente en estas comunidades de conferencias web 00:07:09.966 --> 00:07:10.566 etcétera. 00:07:12.600 --> 00:07:14.966 Y estos algoritmos, lo que hacen es... 00:07:14.966 --> 00:07:18.100 Intenta, en un paso local, aprender algo 00:07:18.100 --> 00:07:20.533 una especie de incrustación, y luego en un entorno global 00:07:20.533 --> 00:07:22.900 paso, asegúrese de que cuando calcule distancias 00:07:22.900 --> 00:07:25.600 Entre las incrustaciones, replican de alguna manera el camino más corto. 00:07:25.600 --> 00:07:26.000 distancias. 00:07:26.533 --> 00:07:30.100 Y veremos que estos son los peores. 00:07:30.100 --> 00:07:31.866 caso por naturaleza, por lo que son un poco conservadores. 00:07:32.433 --> 00:07:35.133 Y así, conmigo y mi colaborador, Shavik 00:07:35.133 --> 00:07:37.100 Dara, lo que hicimos fue analizar estos 00:07:37.100 --> 00:07:39.433 algoritmos en grafos aleatorios homogéneos, que es un 00:07:39.433 --> 00:07:42.500 una clase de gráficos mucho más realista, para intentar 00:07:42.500 --> 00:07:44.866 para obtener garantías de distorsión del caso promedio. 00:07:45.600 --> 00:07:47.166 Así que esto es lo primero que vamos a hacer, 00:07:47.233 --> 00:07:49.233 y luego también voy a mostrar algunos datos empíricos 00:07:49.233 --> 00:07:52.533 resultados donde reemplazamos este paso local que 00:07:52.533 --> 00:07:55.266 Lo aclararé más adelante. 00:07:55.266 --> 00:07:57.166 momentos con una GNN. 00:07:57.466 --> 00:07:59.266 Y esto nos permite tener cosas como 00:07:59.266 --> 00:08:04.266 transferibilidad, todas las buenas propiedades de las GNN. 00:08:04.866 --> 00:08:06.266 Esta será la primera parte, y 00:08:06.266 --> 00:08:08.333 Luego, en la segunda parte, vamos a... 00:08:08.333 --> 00:08:09.733 Ajustar la escala mesoscópica. 00:08:10.266 --> 00:08:12.933 Entonces, aquí, lo que vamos a hacer es que... 00:08:12.933 --> 00:08:14.933 voy a usar este tipo de incrustación llamado el 00:08:14.933 --> 00:08:16.600 Incrustaciones de búsqueda de adyacencia máxima. 00:08:16.733 --> 00:08:20.900 Estas ideas están inspiradas en las cascadas que se producen en la dinámica de la opinión pública. 00:08:21.666 --> 00:08:23.466 Estos son esencialmente el trabajo de mi otro 00:08:23.466 --> 00:08:25.500 Colaboradora, Meher, que es de esta zona. 00:08:26.433 --> 00:08:29.100 Y lo que hacen estas incrustaciones es contar. 00:08:29.866 --> 00:08:31.800 ocurrencias de nodos en saltos múltiples. 00:08:32.000 --> 00:08:34.100 Para qué utilizaremos estas incrustaciones es: 00:08:34.100 --> 00:08:36.266 para reconectar el gráfico de tal manera que estemos 00:08:36.266 --> 00:08:39.100 capturando no solo estas conexiones locales en el 00:08:39.100 --> 00:08:42.600 gráfico, pero también estas conexiones máximamente adyacentes. 00:08:42.800 --> 00:08:43.966 Entonces hay nodos que podrían no ser 00:08:43.966 --> 00:08:46.200 conectados por un borde, pero están en múltiples 00:08:46.200 --> 00:08:50.266 una especie de rutas de múltiples saltos, y eso significa 00:08:50.266 --> 00:08:51.800 Están conectados al máximo de alguna manera. 00:08:53.100 --> 00:08:55.500 Y nuestro objetivo será reconfigurar el 00:08:55.500 --> 00:08:59.166 gráfico, pase este gráfico a través de cualquier arquitectura como 00:08:59.166 --> 00:09:02.066 una GNN o un transformador de grafos, y con suerte 00:09:02.066 --> 00:09:04.933 a través de este recableado, podrá extraer más 00:09:04.933 --> 00:09:06.366 de esta estructura mesoscópica. 00:09:06.733 --> 00:09:10.000 Y aquí veremos que la métrica válida, 00:09:10.166 --> 00:09:12.333 como la métrica apropiada es la resistencia efectiva, 00:09:12.633 --> 00:09:15.300 y que podemos establecer un límite inferior para el 00:09:15.300 --> 00:09:19.266 resistencia efectiva de estos bordes recableados que nosotros 00:09:19.266 --> 00:09:20.100 lo añadiré. 00:09:21.800 --> 00:09:24.233 Bien, comencemos con la primera parte. 00:09:25.833 --> 00:09:28.266 Entonces, el problema que estamos tratando de resolver es... 00:09:28.266 --> 00:09:31.966 La dirección aquí es para aproximar las distancias del camino más corto, 00:09:32.200 --> 00:09:32.300 ¿bien? 00:09:32.366 --> 00:09:33.533 Esto es como un subproblema. 00:09:33.533 --> 00:09:35.233 del problema del camino más corto. 00:09:35.366 --> 00:09:36.166 Es un poco más sencillo. 00:09:36.300 --> 00:09:37.966 No estás intentando encontrar el camino más corto. 00:09:38.000 --> 00:09:39.733 Simplemente estás tratando de encontrar la distancia más corta. 00:09:41.066 --> 00:09:42.966 Sabemos que hay un algoritmo que puedes 00:09:42.966 --> 00:09:46.166 Se utiliza para encontrar problemas de caminos más cortos en particular, 00:09:46.466 --> 00:09:50.533 pero el problema es que encontrar todo exacto 00:09:50.533 --> 00:09:53.500 -distancias entre pares utilizando este algoritmo e incluso simplificaciones 00:09:53.500 --> 00:09:56.300 Su coste es bastante prohibitivo a gran escala, ¿verdad? 00:09:56.400 --> 00:09:58.400 Por lo tanto, su escala es O de N veces 00:09:58.400 --> 00:10:00.000 N más M, donde N es el número 00:10:00.000 --> 00:10:01.300 de nodos y M es el número de 00:10:01.300 --> 00:10:02.100 aristas en el grafo. 00:10:03.300 --> 00:10:06.300 Y así, una idea que se ha explorado 00:10:06.300 --> 00:10:09.366 Mucho por parte de las personas que trabajan en este problema. 00:10:09.900 --> 00:10:12.266 ¿Es esta idea de incrustar nodos en algún 00:10:12.266 --> 00:10:14.900 espacio tal que la distancia entre las incrustaciones 00:10:14.900 --> 00:10:17.366 de los nodos en este espacio se aproximan a 00:10:17.366 --> 00:10:20.466 distancia del gráfico, es decir, la distancia del camino más corto, ¿de acuerdo? 00:10:20.966 --> 00:10:23.000 Y luego la calidad de estas incrustaciones es 00:10:23.000 --> 00:10:25.466 medido por una distorsión multiplicativa, ¿verdad? 00:10:25.533 --> 00:10:28.433 Entonces, si D es la aproximación, 00:10:28.966 --> 00:10:30.800 queremos que sea inferior y superior 00:10:30.800 --> 00:10:31.900 limitado de esta manera. 00:10:32.200 --> 00:10:34.833 Decimos que esta aproximación tiene uno más 00:10:34.833 --> 00:10:38.000 menos distorsión épsilon si está acotada inferiormente por 00:10:38.000 --> 00:10:40.666 uno menos épsilon, la distancia real del camino más corto, 00:10:41.266 --> 00:10:43.200 y limitado superiormente por uno más épsilon, el 00:10:43.200 --> 00:10:45.800 ¿Distancia real del camino más corto, de acuerdo? 00:10:46.166 --> 00:10:48.066 Pasos, un paso local y un paso global. 00:10:48.333 --> 00:10:50.600 El paso local se suele realizar sin conexión a internet. 00:10:50.600 --> 00:10:52.766 Así que hacemos este paso para todos los 00:10:52.766 --> 00:10:53.533 nodos por adelantado. 00:10:54.166 --> 00:10:55.900 Y la forma en que funciona es que tomas una muestra, 00:10:56.100 --> 00:10:57.266 Entonces te dan tu gráfico. 00:10:57.566 --> 00:10:59.600 Aquí simplemente estoy omitiendo los bordes solo para 00:10:59.600 --> 00:11:02.066 hacer que la imagen sea más nítida. 00:11:02.266 --> 00:11:03.966 Pero lo que haces es tomar muestras de lugares emblemáticos. 00:11:03.966 --> 00:11:09.500 conjuntos, conjuntos de puntos de referencia, S0 a SR. Y estos 00:11:09.500 --> 00:11:11.866 son conjuntos de nodos semilla o nodos de referencia. 00:11:12.100 --> 00:11:14.700 Así que aquí los represento con el color naranja. 00:11:14.700 --> 00:11:15.666 nodos. 00:11:16.366 --> 00:11:18.266 Y entonces lo que haces es empezar 00:11:18.266 --> 00:11:20.266 la distancia de cada nodo en el grafo 00:11:20.266 --> 00:11:23.066 al punto de referencia más cercano por conjunto, ¿verdad? 00:11:23.133 --> 00:11:25.700 Así, cada nodo tendrá una dimensión r. 00:11:25.700 --> 00:11:29.133 incrustación donde la j-ésima entrada de esa incrustación 00:11:29.133 --> 00:11:33.166 es la distancia mínima entre usted y un 00:11:33.166 --> 00:11:35.166 elemento de ese conjunto, ¿de acuerdo? 00:11:37.500 --> 00:11:39.400 Esto se hace sin conexión para todos los nodos. 00:11:39.566 --> 00:11:41.000 Normalmente la forma en que la gente hace esto es haciendo 00:11:41.000 --> 00:11:44.200 Búsqueda en amplitud a partir de las semillas o puntos de referencia. 00:11:45.166 --> 00:11:47.366 Y luego almacenas todas estas distancias. 00:11:47.366 --> 00:11:49.000 Obtienes tus incrustaciones de nodos. 00:11:49.166 --> 00:11:51.800 Puedes tener el paso global en un 00:11:51.800 --> 00:11:53.966 ¿Moda basada en consultas, verdad? 00:11:54.000 --> 00:11:55.733 Así que puedo venir a mi servidor o 00:11:55.733 --> 00:11:58.600 mi computadora y decir, quiero aproximar 00:11:58.600 --> 00:12:00.300 El camino más corto entre U y V. 00:12:01.066 --> 00:12:02.766 Entonces, la forma en que haces esto es... 00:12:02.766 --> 00:12:04.966 mira estas incrustaciones y calcula algunas 00:12:04.966 --> 00:12:06.900 una especie de aproximación de la distancia basada en 00:12:06.900 --> 00:12:07.733 la desigualdad triangular. 00:12:10.266 --> 00:12:13.400 Entonces hay dos tipos de formas clásicas 00:12:13.400 --> 00:12:14.000 para hacer esto. 00:12:14.766 --> 00:12:17.000 El primer método te da un límite inferior 00:12:17.500 --> 00:12:21.133 para la distancia real del camino más corto, ¿verdad? 00:12:21.300 --> 00:12:22.966 Entonces estoy escribiendo el límite inferior como el 00:12:22.966 --> 00:12:24.400 subrayar. 00:12:25.133 --> 00:12:26.700 Y luego aquí, quiero decir, el paso local 00:12:26.700 --> 00:12:28.500 Es exactamente como lo describí, ¿verdad? 00:12:28.566 --> 00:12:31.700 Estás creando esa incrustación por distancias desde cada 00:12:31.700 --> 00:12:33.600 nodo a la semilla más cercana en cada uno 00:12:33.600 --> 00:12:34.066 de los conjuntos. 00:12:34.500 --> 00:12:36.333 Y luego en el paso global, y esto 00:12:36.333 --> 00:12:38.966 Se llama algoritmo de Lugan, lo que haces es 00:12:38.966 --> 00:12:42.300 utilizas la desigualdad triangular inversa y 00:12:42.300 --> 00:12:44.600 obtener este límite inferior, pero esencialmente tomando el 00:12:44.600 --> 00:12:46.866 Norma L infinito de la diferencia entre la 00:12:46.866 --> 00:12:47.266 incrustaciones. 00:12:47.533 --> 00:12:49.300 Entonces, lo que esto hace en la práctica es 00:12:49.300 --> 00:12:54.166 está tratando de encontrar la distancia máxima entre 00:12:54.166 --> 00:12:56.433 las incrustaciones en términos de coordenadas, ¿verdad? 00:12:56.500 --> 00:12:58.500 Así que estás tratando de encontrar el conjunto 00:12:58.900 --> 00:13:01.866 que alcanza esta distancia máxima. 00:13:04.800 --> 00:13:07.600 Y luego está otro enfoque que se propuso. 00:13:07.600 --> 00:13:09.866 en este algoritmo por, en este artículo, por 00:13:09.866 --> 00:13:14.266 Dasarma y otros que te dan una ventaja 00:13:14.266 --> 00:13:14.966 atado, ¿verdad? 00:13:14.966 --> 00:13:19.000 Así que le da a esta D línea superior esa parte superior 00:13:19.000 --> 00:13:20.666 delimita la distancia real del camino más corto. 00:13:21.000 --> 00:13:24.100 Y aquí, nodos semilla, lo que también hacemos 00:13:24.100 --> 00:13:27.500 es almacenamos el índice real del 00:13:27.500 --> 00:13:30.966 semilla en SJ que logra esta distancia, ¿verdad? 00:13:31.000 --> 00:13:33.000 Entonces queremos saber el tamaño, usted 00:13:33.000 --> 00:13:36.333 saber, como el tamaño de la distancia de 00:13:36.333 --> 00:13:38.500 el nodo de cada conjunto, que es el 00:13:38.500 --> 00:13:41.566 nodo en ese sentido que está más cerca de 00:13:41.566 --> 00:13:42.500 ¿Tú, de acuerdo? 00:13:43.100 --> 00:13:46.800 Entonces, ¿usando estos dos tipos de vectores, verdad? 00:13:46.933 --> 00:13:48.933 Uno en nuestro vector dimensional y el otro 00:13:48.933 --> 00:13:51.200 un escalar por nodo. 00:13:51.566 --> 00:13:54.100 Cuando realizamos el paso global, utilizamos 00:13:54.100 --> 00:13:56.900 la desigualdad triangular, no la inversa, sino la inversa 00:13:56.900 --> 00:14:01.100 desigualdad triangular ahora para acotar superiormente el más corto 00:14:01.100 --> 00:14:04.766 distancia del camino por el mínimo entre la suma 00:14:04.766 --> 00:14:09.800 entre OXUJ y FXPJ de tal manera que las semillas 00:14:09.800 --> 00:14:12.700 que alcancen la distancia mínima en la semilla 00:14:12.700 --> 00:14:14.666 ¿El partido de SJ está programado, verdad? 00:14:14.800 --> 00:14:17.766 Esto es lo que tengo aquí, pero 00:14:17.766 --> 00:14:20.400 para aproximar la distancia entre este U1 y 00:14:20.400 --> 00:14:22.733 U2 aquí, necesito tener algo en común 00:14:22.733 --> 00:14:23.833 semilla, ¿verdad? 00:14:24.366 --> 00:14:26.300 Y por eso necesitas este extra 00:14:26.300 --> 00:14:27.400 Incrustando aquí. 00:14:28.500 --> 00:14:28.966 ¿Qué ocurre? 00:14:29.600 --> 00:14:30.400 Lo lamento. 00:14:31.566 --> 00:14:32.766 Sí, dejaré de moverme. 00:14:33.666 --> 00:14:33.900 Bueno. 00:14:36.066 --> 00:14:40.300 Muy bien, estos dos son algoritmos clásicos. 00:14:40.300 --> 00:14:42.200 Y como dije, estos algoritmos no significan 00:14:42.200 --> 00:14:46.000 Cualquier cosa si no tienen garantías de distorsión, ¿verdad? 00:14:46.066 --> 00:14:48.633 Por lo tanto, necesitamos una garantía de distorsión tanto para 00:14:48.633 --> 00:14:50.433 El algoritmo de Bourgan y el algoritmo de Sarma. 00:14:51.100 --> 00:14:53.500 El algoritmo de Bourgan nos da un límite inferior. 00:14:53.766 --> 00:14:56.300 Y este teorema de aquí, que se basa en 00:14:56.300 --> 00:14:59.700 El teorema de incrustación de Bourgan, la distorsión del límite inferior. 00:15:00.966 --> 00:15:04.966 Este teorema en realidad, quiero decir, no necesariamente 00:15:04.966 --> 00:15:07.300 aplicar solo al más corto de este mismo 00:15:07.300 --> 00:15:10.366 importante artículo de Bourgan y luego más tarde por 00:15:10.366 --> 00:15:14.333 Matuszek, donde esencialmente muestran la distorsión de 00:15:14.333 --> 00:15:17.100 ¿Incrustar espacios métricos en espacios de Hilbert, verdad? 00:15:17.100 --> 00:15:19.300 Porque siempre pierdes algo cuando lo haces. 00:15:19.300 --> 00:15:19.566 eso. 00:15:19.900 --> 00:15:22.900 Y este es básicamente ese teorema aplicado a 00:15:22.900 --> 00:15:24.166 este problema en particular. 00:15:25.466 --> 00:15:28.700 Entonces, lo que dice el teorema es que, dado 00:15:28.700 --> 00:15:33.233 un gráfico suficientemente grande, para cualquier constante C 00:15:33.233 --> 00:15:36.466 que usted corrija, existen incrustaciones óptimas, que 00:15:36.466 --> 00:15:38.666 ¿Son estas incrustaciones de estrella X que tengo? 00:15:38.666 --> 00:15:43.266 aquí, con dimensión al menos N a la 00:15:43.266 --> 00:15:46.166 uno sobre C log N, de tal manera que el 00:15:46.166 --> 00:15:51.100 El estimador del límite inferior tiene distorsión acotada, donde el 00:15:51.100 --> 00:15:53.366 La distorsión viene dada por ese uno sobre dos 00:15:53.366 --> 00:15:54.100 C menos uno. 00:15:55.000 --> 00:15:55.100 ¿Bueno? 00:15:55.800 --> 00:15:57.766 Por ejemplo, si quisieras obtener 00:15:57.766 --> 00:16:02.500 distorsión del orden, por ejemplo, veamos aquí. 00:16:04.033 --> 00:16:06.333 Entonces, si hacemos 1.5, esto sería 00:16:06.333 --> 00:16:07.133 ser la mitad, ¿verdad? 00:16:07.133 --> 00:16:09.300 Entonces obtendrías algo como a 00:16:09.300 --> 00:16:11.900 uno, como uno sobre 1,5 log N 00:16:11.900 --> 00:16:15.600 incrustaciones que te dan una distorsión de una 00:16:15.600 --> 00:16:16.000 La mitad está allí. 00:16:17.733 --> 00:16:18.133 Bueno. 00:16:21.433 --> 00:16:24.000 Luego, además de tener una garantía de distorsión para la 00:16:24.000 --> 00:16:24.633 límite inferior, ¿verdad? 00:16:24.700 --> 00:16:27.266 Así que para el algoritmo de Bourgan, también tenemos distorsión 00:16:27.266 --> 00:16:30.400 garantías para el límite superior de ese más 00:16:30.400 --> 00:16:31.166 artículo reciente. 00:16:31.833 --> 00:16:34.733 Y en ese artículo, además de proponer este algoritmo, 00:16:34.900 --> 00:16:37.633 También ofrecen garantías en cuanto se establecen las semillas. 00:16:37.633 --> 00:16:40.933 Tengo la talla dos a la J, ¿de acuerdo? 00:16:40.933 --> 00:16:43.000 Con J variando desde cero hasta el suelo 00:16:43.000 --> 00:16:44.266 del logaritmo N. 00:16:45.500 --> 00:16:47.166 Y la razón por la que necesitas esta construcción 00:16:47.166 --> 00:16:50.633 una de las razones es porque, recuerda 00:16:50.633 --> 00:16:53.000 que dije que siempre necesitas 00:16:53.000 --> 00:16:54.100 tienen esta semilla común. 00:16:59.066 --> 00:17:01.333 Siempre necesitas tener la semilla común. 00:17:01.500 --> 00:17:02.800 Y por eso siempre necesitas tener en 00:17:02.800 --> 00:17:07.000 Al menos un conjunto que tenga la talla uno, ¿verdad? 00:17:07.000 --> 00:17:11.600 Porque es posible que no encuentres semillas coincidentes en 00:17:11.600 --> 00:17:11.966 los demás. 00:17:12.133 --> 00:17:15.733 Tienes que poner S a cero, te da 00:17:15.733 --> 00:17:17.200 esa aproximación de desigualdad triangular. 00:17:18.100 --> 00:17:19.800 Y lo que dice este teorema es que usted 00:17:19.800 --> 00:17:23.366 ¿Obtienes dos C menos una garantía de distorsión, verdad? 00:17:23.400 --> 00:17:26.633 Para el límite superior, para su límite superior 00:17:26.633 --> 00:17:31.333 aproximación de la ruta más corta con incrustaciones X estrella 00:17:31.333 --> 00:17:34.100 con dimensión al menos N elevada a la una 00:17:34.100 --> 00:17:34.866 sobre C log N. 00:17:35.166 --> 00:17:36.200 Vale, entonces son muy similares. 00:17:37.000 --> 00:17:37.966 Garantías de distorsión. 00:17:39.133 --> 00:17:41.100 Y la misma dimensión mínima de incrustación. 00:17:43.300 --> 00:17:47.233 Ahora bien, ¿cuál es el problema con estas distorsiones? 00:17:47.233 --> 00:17:47.600 ¿resultados? 00:17:48.000 --> 00:17:49.766 El problema con ellos es que son 00:17:49.766 --> 00:17:54.200 el peor caso en la naturaleza en el sentido de que 00:17:54.200 --> 00:17:56.866 se mantienen incluso para, como imagina un gráfico 00:17:56.866 --> 00:17:59.300 donde aproximar los caminos más cortos es muy difícil. 00:17:59.400 --> 00:18:01.400 Por ejemplo, un gráfico donde podrías tener 00:18:01.400 --> 00:18:04.966 como una especie de masa conectada agradable, pero 00:18:04.966 --> 00:18:07.166 tienes como caminos muy largos, como 00:18:07.166 --> 00:18:08.500 patas de araña o algo así, ¿verdad? 00:18:08.933 --> 00:18:11.933 Aproximar los caminos más cortos en este grafo es muy 00:18:11.933 --> 00:18:14.600 difícil si no pruebas una semilla en 00:18:14.600 --> 00:18:15.200 ese camino. 00:18:16.766 --> 00:18:19.500 Por lo tanto, estas garantías se mantienen incluso en ese caso. 00:18:19.566 --> 00:18:21.600 Así que puedes imaginar que son bastante holgados, 00:18:21.666 --> 00:18:21.866 ¿bien? 00:18:22.033 --> 00:18:24.400 Y ese es el peor de los casos. 00:18:25.800 --> 00:18:30.000 Y además, porque estos tamaños de incrustación no son 00:18:30.000 --> 00:18:32.566 Esto se vuelve prohibitivo a pequeña escala. 00:18:33.133 --> 00:18:35.500 Y como dije, es pesimista para el 00:18:35.500 --> 00:18:37.166 Gráficos estructurados que realmente tenemos, ¿verdad? 00:18:37.200 --> 00:18:38.666 Y en realidad lo que hice a partir de los dos 00:18:38.666 --> 00:18:40.166 Las diapositivas anteriores a esta son solo 00:18:40.166 --> 00:18:44.033 expresó la dimensión de incrustación mínima en términos de 00:18:44.033 --> 00:18:46.166 épsilon, porque ahora quiero tener uno menos 00:18:46.166 --> 00:18:48.633 épsilon, uno más épsilon distorsión, es decir, distorsión limpia. 00:18:49.166 --> 00:18:53.000 Y así ajusté el valor mínimo de incrustación. 00:18:53.000 --> 00:18:53.300 tamaño. 00:18:56.066 --> 00:19:00.000 Bien, entonces, ¿cuál es su gráfico de casos promedio? 00:19:00.100 --> 00:19:00.266 ¿bien? 00:19:00.266 --> 00:19:01.866 ¿Qué gráficos son más realistas? 00:19:01.866 --> 00:19:04.566 ¿Y más cercano a lo que tienes en la práctica? 00:19:04.966 --> 00:19:09.233 Un modelo que se usa mucho para modelar 00:19:09.233 --> 00:19:11.800 Este tipo de gráficos constituye el modelo de grafo aleatorio no homogéneo. 00:19:12.666 --> 00:19:16.100 Y este modelo es básicamente una extensión de 00:19:16.100 --> 00:19:17.700 un modelo de bloques estocásticos. 00:19:18.000 --> 00:19:21.966 Entonces, lo que sucede es que en este modelo, 00:19:22.066 --> 00:19:24.700 Cada nodo tiene un tipo, ¿verdad? 00:19:24.766 --> 00:19:26.166 Entonces cada nodo pertenece a algo así como 00:19:26.166 --> 00:19:27.966 un tipo o una familia, y el borde 00:19:27.966 --> 00:19:30.300 La probabilidad dependerá del tipo de punto final. 00:19:30.300 --> 00:19:32.200 Entonces tendrás una matriz D, que es 00:19:32.200 --> 00:19:33.833 llamada matriz de afinidad que es una especie de 00:19:33.833 --> 00:19:36.900 codificando la afinidad entre nodos de diferentes tipos. 00:19:38.966 --> 00:19:41.733 Y lo que haces es para 00:19:41.733 --> 00:19:44.766 calcular la probabilidad de que dos nodos se conecten en 00:19:44.766 --> 00:19:48.433 este gráfico, divides la entrada correspondiente de 00:19:48.433 --> 00:19:52.300 D por el número de nodos en el 00:19:52.300 --> 00:19:55.500 una especie de comunidad de algo así como 00:19:55.500 --> 00:19:56.366 ¿Tu vecino, verdad? 00:19:57.100 --> 00:19:59.033 Entonces D no es una probabilidad, sino cuando 00:19:59.033 --> 00:20:01.833 tomas la proporción de eso con el 00:20:01.833 --> 00:20:04.766 tamaño de la comunidad, tamaño de la comunidad de tu vecino, obtienes 00:20:04.766 --> 00:20:05.466 una probabilidad. 00:20:06.866 --> 00:20:08.500 Este modelo es muy general, por lo que incluye 00:20:08.500 --> 00:20:11.133 cosas como el modelo de bloques estocásticos o el 00:20:11.133 --> 00:20:12.600 Serenium cuando solo hay un tipo. 00:20:13.733 --> 00:20:16.966 Y por eso nuestra idea es intentar 00:20:16.966 --> 00:20:20.966 derivar esas garantías de distorsión ahora, no solo para 00:20:20.966 --> 00:20:23.000 estos grafos aleatorios no homogéneos que son mejores 00:20:23.000 --> 00:20:25.366 modelo de su gráfico típico que encuentra 00:20:25.366 --> 00:20:27.266 en el mundo real. 00:20:28.833 --> 00:20:31.300 Así que antes de hablar sobre nuestros resultados de distorsión, 00:20:31.333 --> 00:20:32.633 Solo quiero darte una idea. 00:20:32.633 --> 00:20:34.400 de la idea de la prueba. 00:20:36.200 --> 00:20:39.400 Como dije antes, en estos algoritmos, 00:20:39.600 --> 00:20:41.300 estos algoritmos locales globales, seguro que hay uno 00:20:41.300 --> 00:20:44.766 aproximación de trayectoria, lo que haces es efectivamente, 00:20:45.100 --> 00:20:47.000 Para calcular las incrustaciones, debes hacer lo siguiente: 00:20:47.000 --> 00:20:48.900 Búsqueda en amplitud desde las semillas, ¿verdad? 00:20:49.466 --> 00:20:50.900 Búsqueda en amplitud, puedes pensarlo 00:20:50.900 --> 00:20:52.266 como exploración local, ¿verdad? 00:20:52.333 --> 00:20:54.600 Entonces soy un nodo, miro mi 00:20:54.600 --> 00:20:56.233 vecinos de un salto, luego mis vecinos de dos saltos, 00:20:56.700 --> 00:20:57.333 etcétera. 00:20:57.966 --> 00:21:00.966 Y como una especie de dinámica 00:21:00.966 --> 00:21:02.266 proceso, puedes pensar en esto como un 00:21:02.266 --> 00:21:03.333 proceso de ramificación, ¿verdad? 00:21:03.366 --> 00:21:05.733 Y en particular, si tiene varios tipos, 00:21:05.866 --> 00:21:08.633 Este será un proceso de ramificación de múltiples tipos. 00:21:08.633 --> 00:21:12.433 con la matriz media dada por D, la afinidad 00:21:12.433 --> 00:21:12.933 matriz. 00:21:14.833 --> 00:21:17.433 Lo que puedes demostrar es que esta ramificación 00:21:17.433 --> 00:21:19.400 proceso, que es básicamente, quiero decir, esto es 00:21:19.400 --> 00:21:22.800 llamado a, es algo así como un binomio 00:21:22.800 --> 00:21:25.700 proceso de ramificación, creo que se llama Galton 00:21:25.700 --> 00:21:28.633 -Proceso Watson, y básicamente, es el proceso donde, 00:21:28.733 --> 00:21:30.933 cada nodo cuando se ramifica, tiene 00:21:30.933 --> 00:21:34.566 una serie de tipos de vecinos dados por 00:21:34.566 --> 00:21:36.266 la media del proceso, que en este 00:21:36.266 --> 00:21:39.333 En este caso, si tienes la matriz de afinidad D, 00:21:39.700 --> 00:21:41.566 eso significa que va a ser lambda uno, 00:21:41.666 --> 00:21:43.766 el valor propio formal de mostrar. 00:21:44.800 --> 00:21:48.233 Utilizando esta aproximación del proceso de ramificación, se obtiene que el 00:21:48.233 --> 00:21:50.600 límite del vecindario de k saltos del nodo 00:21:50.600 --> 00:21:54.333 U es de orden lambda uno al 00:21:54.333 --> 00:21:55.233 Vale, ¿verdad? 00:21:57.033 --> 00:22:00.100 Y lo que mostramos a continuación, después de mostrar 00:22:00.100 --> 00:22:06.266 estas concentraciones de ambos tamaños de límite de 00:22:06.266 --> 00:22:09.833 el barrio k-hop y también el tamaño 00:22:09.833 --> 00:22:11.800 de todo el barrio k-hop, es tu 00:22:11.800 --> 00:22:15.733 capaz de demostrar que las distancias típicas se concentran utilizando 00:22:15.733 --> 00:22:17.733 concentración de variables aleatorias de Bernoulli. 00:22:18.366 --> 00:22:21.766 Esencialmente, DUV, donde DUV es la distancia típica, 00:22:22.533 --> 00:22:27.433 se concentra alrededor de lambda base logarítmica uno de n, 00:22:27.933 --> 00:22:28.333 ¿bueno? 00:22:29.133 --> 00:22:32.133 Y entonces esta distancia típica es lo que es 00:22:32.133 --> 00:22:34.333 nos van a dar nuestra garantía de distorsión y 00:22:34.333 --> 00:22:36.800 La concentración a su alrededor es lo que nos va a dar 00:22:36.800 --> 00:22:37.700 Nuestra garantía de distorsión. 00:22:39.133 --> 00:22:41.900 Este es nuestro resultado. 00:22:42.133 --> 00:22:44.133 Así que usando esos dos algoritmos para el inferior 00:22:44.133 --> 00:22:46.733 límite y límite superior, lo que mostramos 00:22:46.733 --> 00:22:50.833 es que bajo condiciones de regularidad limitadas en el 00:22:50.833 --> 00:22:54.600 modelo de grafo aleatorio no homogéneo, aquellos hitos o semillas 00:22:54.600 --> 00:22:58.966 Las incrustaciones basadas en logran una distorsión de uno más menos épsilon. 00:22:58.966 --> 00:23:02.433 con alta probabilidad con dimensión de incrustación, por lo que para 00:23:02.433 --> 00:23:06.200 el límite inferior, al menos n al 00:23:06.200 --> 00:23:09.000 uno menos épsilon log lambda uno n, y 00:23:09.000 --> 00:23:12.033 entonces esta expresión más complicada para uno más 00:23:12.033 --> 00:23:14.600 épsilon pero en la práctica, quiero decir, si tú 00:23:14.600 --> 00:23:19.300 Olvídate de este mínimo aquí, obtienes algo 00:23:19.300 --> 00:23:23.200 como, es como uno, creo que es uno 00:23:23.200 --> 00:23:24.633 más épsilon o algo así. 00:23:27.900 --> 00:23:28.966 Sí, gracias. 00:23:29.700 --> 00:23:31.933 Sí, así es. 00:23:32.366 --> 00:23:36.100 Entonces, mucho mejor, de acuerdo. 00:23:36.766 --> 00:23:39.266 Así que hay algunas cosas interesantes que decir 00:23:39.266 --> 00:23:40.366 ¿Se fijan aquí, verdad? 00:23:40.400 --> 00:23:41.900 Esto no se ve mucho mejor que el 00:23:41.900 --> 00:23:43.166 incrustaciones que teníamos antes, pero son 00:23:43.166 --> 00:23:43.733 Un poco mejor. 00:23:44.166 --> 00:23:45.400 Entonces, lo primero que notas es 00:23:45.400 --> 00:23:47.200 que esto ahora está gobernado por el espectro 00:23:47.200 --> 00:23:50.600 radio, lambda uno de la matriz de afinidad y 00:23:50.600 --> 00:23:53.133 este eta n aquí es el tipo mínimo 00:23:53.133 --> 00:23:54.400 exponente de tamaño, ¿verdad? 00:23:54.433 --> 00:23:56.533 Así que esto es una especie de control para no 00:23:56.533 --> 00:24:01.733 tener tipos o comunidades muy desequilibradas, y qué 00:24:01.733 --> 00:24:04.133 lo que ves es que los tipos más equilibrados... 00:24:04.133 --> 00:24:07.200 te dan incrustaciones más pequeñas, y eso aunque 00:24:07.200 --> 00:24:10.933 Esto todavía no se ve increíble, es polinómicamente más pequeño. 00:24:10.933 --> 00:24:13.833 que esos peores casos, no garantías de distorsión, el 00:24:13.833 --> 00:24:18.000 tamaños de incrustación en el peor de los casos aproximadamente de n a 00:24:18.000 --> 00:24:19.000 épsilon sobre dos. 00:24:19.533 --> 00:24:22.200 Entonces hay una especie de ganancia polinómica que 00:24:22.200 --> 00:24:25.066 tienes aquí cuando te enfocas en lo homogéneo 00:24:25.066 --> 00:24:25.833 o no gráficos, ¿verdad? 00:24:25.866 --> 00:24:27.633 Como cuando te olvidas de los gráficos del peor escenario. 00:24:30.133 --> 00:24:31.666 Ese fue nuestro principal resultado. 00:24:31.833 --> 00:24:33.233 Otra cosa que puedes hacer es... 00:24:33.233 --> 00:24:35.533 Esto se puede extender al caso de continuidad 00:24:35.533 --> 00:24:36.033 tipos. 00:24:36.766 --> 00:24:41.133 Entonces, en lugar de tener como un conjunto finito 00:24:41.133 --> 00:24:43.033 de tipos como en un modelo de bloques estocásticos, 00:24:43.033 --> 00:24:45.400 podrías tener infinitos tipos, por ejemplo, 00:24:45.600 --> 00:24:46.800 como en un grafón, ¿verdad? 00:24:47.633 --> 00:24:49.233 Y ahora tu D ya no es 00:24:49.233 --> 00:24:53.433 una matriz, es un núcleo, y esto permite 00:24:53.433 --> 00:24:55.600 usted para extender estos resultados a un nivel aún mayor. 00:24:55.600 --> 00:24:59.200 un conjunto más amplio de gráficos más allá de SBM y Erdos 00:24:59.200 --> 00:25:01.900 -Renyi, como los gráficos de Chung-Liu y otros, 00:25:02.533 --> 00:25:05.500 y los límites de distorsión son muy similares. 00:25:05.700 --> 00:25:08.866 La forma en que extiendes ese resultado de distorsión a 00:25:08.866 --> 00:25:12.166 estos gráficos con infinitos tipos eres tú 00:25:12.166 --> 00:25:16.800 una especie de sándwich en el núcleo, el núcleo continuo, 00:25:16.900 --> 00:25:18.900 mediante núcleos de función escalonada y considere esos pasos 00:25:18.900 --> 00:25:22.000 Los núcleos de las funciones deben ser grafos con tipos finitos. 00:25:22.300 --> 00:25:25.433 Ese fue el tipo de contribución teórica a 00:25:25.433 --> 00:25:30.000 derivar estas garantías de distorsión para más realistas, más 00:25:30.000 --> 00:25:31.000 Gráficos del caso promedio. 00:25:31.800 --> 00:25:34.400 En el aspecto numérico, lo que hicimos fue 00:25:34.400 --> 00:25:37.433 reemplazamos el paso de búsqueda en amplitud en 00:25:37.433 --> 00:25:41.533 el paso local de esos algoritmos con un 00:25:41.533 --> 00:25:42.900 ¿Un sustituto del camino más corto, verdad? 00:25:42.900 --> 00:25:44.933 Así que se entrena simplemente mediante aprendizaje por imitación. 00:25:44.933 --> 00:25:47.800 imitar la búsqueda en amplitud o el camino más corto desde 00:25:47.800 --> 00:25:48.233 las semillas. 00:25:50.200 --> 00:25:52.233 Aunque estas GNN no son adecuadas para 00:25:52.233 --> 00:25:55.733 cálculo de la ruta más corta larga, para rutas más cortas cortas, 00:25:55.900 --> 00:25:58.966 Lo hacen bastante bien. 00:26:00.133 --> 00:26:02.100 Y lo que hicimos fue entrenar en 00:26:02.100 --> 00:26:02.933 Gráficos pequeños, ¿verdad? 00:26:02.933 --> 00:26:05.500 Entrenamos en un pequeño conjunto de 100 nodos y 00:26:05.500 --> 00:26:06.533 grafo aleatorio homogéneo. 00:26:06.733 --> 00:26:08.233 Este era un grafo aleatorio de Erdos-Renyi. 00:26:08.900 --> 00:26:11.666 Y luego se transfirió a gráficos hasta 32 00:26:11.666 --> 00:26:13.700 veces más grande. 00:26:14.433 --> 00:26:15.866 Y lo que vemos aquí en esta diapositiva 00:26:15.866 --> 00:26:17.733 es, entonces cuando tus gráficos son bastante dispersos, 00:26:17.866 --> 00:26:17.966 ¿bien? 00:26:18.000 --> 00:26:19.833 Entonces cuando lambda es como tres y 00:26:19.833 --> 00:26:24.800 cuatro, que está casi fuera del rango supercrítico 00:26:24.800 --> 00:26:28.766 régimen para Erdos-Renyi, lo que ves es 00:26:28.766 --> 00:26:32.600 Que la búsqueda en amplitud siempre gana. 00:26:32.900 --> 00:26:34.533 Pero una vez que te vuelves un poco más denso, 00:26:34.633 --> 00:26:36.233 entonces tu lambda está en cinco o seis, 00:26:36.933 --> 00:26:40.866 Con el tiempo, se obtiene un mejor MSC con las GNN. 00:26:40.866 --> 00:26:43.500 a un coste mucho menor, ¿verdad? 00:26:43.600 --> 00:26:45.100 Así que como tienes que hacerlo, esto es para 00:26:45.100 --> 00:26:47.033 las GNN, así que tienes que hacer paso 00:26:47.033 --> 00:26:49.900 Menos cálculos, especialmente para gráficos de gran tamaño porque 00:26:49.900 --> 00:26:51.433 La búsqueda en amplitud es exhaustiva, ¿verdad? 00:26:51.533 --> 00:26:54.233 Las GNN solo llegan hasta k saltos, 00:26:54.933 --> 00:26:55.600 capas l. 00:26:58.800 --> 00:27:00.766 Luego también realizamos este experimento de verdad. 00:27:00.766 --> 00:27:04.400 -redes mundiales, todavía utilizando nuestras GNN entrenadas en 00:27:04.400 --> 00:27:06.566 esos gráficos sintéticos. 00:27:07.266 --> 00:27:10.600 Y lo que hicimos aquí fue, de nuevo, 00:27:10.866 --> 00:27:15.200 transferimos esas GNN a estos mundos reales. 00:27:15.200 --> 00:27:19.200 gráficos con un orden de 10.000 nodos. 00:27:19.733 --> 00:27:21.566 Y lo que vimos aquí fue que, sí, 00:27:21.666 --> 00:27:24.366 como por ejemplo, partiendo de un cierto 00:27:24.366 --> 00:27:26.700 tamaño del gráfico, obtienes un MSC más bajo cuando 00:27:26.700 --> 00:27:30.600 usar GNN para aproximar la amplitud del límite inferior 00:27:30.600 --> 00:27:31.166 -primera búsqueda. 00:27:31.800 --> 00:27:33.966 Y nuestro principal objetivo aquí era simplemente 00:27:33.966 --> 00:27:39.666 ver, ¿cómo se comportan estos gráficos aleatorios no homogéneos? 00:27:39.666 --> 00:27:43.300 ¿Practicar como un gráfico promedio del mundo real? 00:27:44.933 --> 00:27:48.500 Y dados estos resultados, sentimos que ellos 00:27:48.500 --> 00:27:52.466 deben comportarse lo suficientemente como estos IHG para el 00:27:52.466 --> 00:27:53.200 teoría para sostener. 00:27:54.966 --> 00:27:57.966 Bien, este es el final de la parte 00:27:57.966 --> 00:27:58.266 uno. 00:27:58.900 --> 00:28:01.000 Supongo que ahora puedo responder preguntas si 00:28:01.000 --> 00:28:03.433 ¿Hay alguna pregunta antes de que continúe? 00:28:03.433 --> 00:28:04.200 a la segunda parte. 00:28:08.066 --> 00:28:11.600 Entonces, la pregunta que vi aquí fue cómo 00:28:11.600 --> 00:28:12.800 para seleccionar los conjuntos de semillas. 00:28:13.100 --> 00:28:16.200 Así que en la práctica, simplemente los pruebas en 00:28:16.200 --> 00:28:20.033 Es algo aleatorio, pero es un problema importante, ¿verdad? 00:28:20.066 --> 00:28:22.200 Y puedes encontrar formas más inteligentes de hacerlo. 00:28:22.200 --> 00:28:22.300 él. 00:28:22.333 --> 00:28:24.600 Por ejemplo, creo que la mejor manera 00:28:24.600 --> 00:28:26.100 para hacerlo es tomar muestras de semillas con 00:28:26.100 --> 00:28:27.333 Alta centralidad, ¿verdad? 00:28:27.366 --> 00:28:30.633 Porque no van a ser solo muy locales 00:28:30.633 --> 00:28:32.266 Conectado, pero muy central en el gráfico. 00:28:33.333 --> 00:28:39.200 De acuerdo, entonces seguiré adelante. 00:28:39.566 --> 00:28:42.833 Entonces, en la segunda parte, como mencioné 00:28:42.833 --> 00:28:44.400 antes, lo que vamos a hacer es que estamos 00:28:44.400 --> 00:28:47.033 voy a intentar recablear los gráficos de tal manera 00:28:47.033 --> 00:28:50.966 en cuanto a preservar o explotar la estructura mesoscópica 00:28:50.966 --> 00:28:54.166 un poco mejor en el procesamiento de señales y 00:28:54.166 --> 00:28:56.100 pipelines de aprendizaje automático. 00:28:57.633 --> 00:29:00.133 Y la razón de ello es porque ambos 00:29:00.133 --> 00:29:03.666 Las GNN y los transformadores de grafos pueden tener dificultades en esto. 00:29:03.666 --> 00:29:05.200 Escala mesoscópica, ¿verdad? 00:29:05.200 --> 00:29:09.066 Entonces, redes neuronales gráficas o paso de mensajes convolucionales 00:29:09.066 --> 00:29:11.566 GNN, se agregan sobre vecindarios de k saltos donde 00:29:11.566 --> 00:29:13.266 Normalmente quiero que k sea pequeño. 00:29:14.200 --> 00:29:16.533 Por lo tanto, este campo receptivo es local. 00:29:17.900 --> 00:29:20.166 Y como mencioné anteriormente, en algunas situaciones, 00:29:20.266 --> 00:29:24.100 Es posible que tengas dificultades para acceder a las comunidades. 00:29:24.100 --> 00:29:25.566 y cuellos de botella y ese tipo de cosas. 00:29:26.800 --> 00:29:29.800 A veces la gente lo llama alisado excesivo, aplastamiento excesivo, 00:29:30.000 --> 00:29:30.166 ¿bien? 00:29:30.800 --> 00:29:33.066 Y luego, cuando se trata de transformadores de gráficos 00:29:33.066 --> 00:29:37.500 con atención intensa, tienen, en cierto modo, 00:29:37.766 --> 00:29:39.100 Quiero decir, si no vas a usar el 00:29:39.100 --> 00:29:42.100 estructura del gráfico, derecha, para calcular sus pares de atención, 00:29:42.233 --> 00:29:44.533 De alguna manera pierdes ese gráfico anterior. 00:29:44.533 --> 00:29:45.900 Es lo que hace que las GNN funcionen tan bien. 00:29:46.366 --> 00:29:48.766 Y además, tienes esta O de N 00:29:48.766 --> 00:29:51.300 atención cuadrada que es muy prohibitiva para grandes 00:29:51.300 --> 00:29:51.666 gráficos. 00:29:53.133 --> 00:29:57.000 Al mismo tiempo, ya estoy motivado, ¿verdad? 00:29:57.033 --> 00:29:57.933 Pero como nosotros, 00:30:10.333 --> 00:30:12.633 Y luego, cuando se trata de transformadores de gráficos 00:30:12.633 --> 00:30:17.100 con atención intensa, tienen algo así como, 00:30:17.300 --> 00:30:18.666 Quiero decir, si no vas a usar el 00:30:18.666 --> 00:30:21.700 estructura del gráfico, derecha, para calcular sus pares de atención, 00:30:21.800 --> 00:30:24.100 De alguna manera pierdes ese gráfico anterior. 00:30:24.100 --> 00:30:27.233 hace que las GNN funcionen tan bien y además usted 00:30:27.233 --> 00:30:29.233 tener esta atención O de N al cuadrado que 00:30:29.233 --> 00:30:31.233 resulta muy prohibitivo para gráficos grandes. 00:30:32.633 --> 00:30:35.866 Al mismo tiempo, y esto ya lo he dicho 00:30:35.866 --> 00:30:40.100 motivados, correcto, pero como queremos en 00:30:40.100 --> 00:30:42.000 algunos problemas, en algunos problemas las representaciones que 00:30:42.000 --> 00:30:46.600 queremos aprender o diseñar, ellos, nosotros 00:30:46.600 --> 00:30:48.400 quieren que reflejen cosas como las comunidades y 00:30:48.400 --> 00:30:48.966 cuellos de botella. 00:30:49.266 --> 00:30:51.900 Una cosa que hace eso son los saltos múltiples 00:30:51.900 --> 00:30:52.600 paseos, ¿verdad? 00:30:52.600 --> 00:30:55.233 Entonces, si tomas varios, digamos, paseos aleatorios 00:30:55.233 --> 00:30:57.766 de longitud suficientemente grande y uno tiene algo así como 00:30:57.766 --> 00:31:00.266 estadísticas promedio que usted recopila en estas caminatas, 00:31:01.366 --> 00:31:04.100 En gráficos bien comportados, puedes 00:31:04.100 --> 00:31:07.033 obtener, cada uno recablea el gráfico promoviendo estos 00:31:07.033 --> 00:31:09.433 pares que aparecen repetidamente en el 00:31:09.433 --> 00:31:13.033 mismos paseos con múltiples saltos. 00:31:16.500 --> 00:31:20.433 Para ello, vamos a utilizar 00:31:20.433 --> 00:31:26.000 esta idea de dinámica de contagio desde la opinión 00:31:26.000 --> 00:31:29.000 dinámica y vamos a usar dos qué 00:31:29.000 --> 00:31:31.900 llaman reglas de cascada para descubrir este mesoscópico 00:31:31.900 --> 00:31:36.266 estructura, búsqueda de adyacencia máxima y búsqueda de adyacencia por umbral. 00:31:36.566 --> 00:31:39.500 Entonces, la forma en que funcionan es que empiezan 00:31:39.500 --> 00:31:40.700 con una semilla aleatoria. 00:31:42.866 --> 00:31:46.700 Además de activar esta semilla aleatoria en el paso cero, 00:31:46.800 --> 00:31:49.300 También activas un conjunto aleatorio de nodos. 00:31:49.300 --> 00:31:52.400 y luego en cada paso lo que vas a hacer 00:31:52.400 --> 00:31:55.700 lo que tienes que hacer es activar el 00:31:55.700 --> 00:31:58.900 nodo inactivo con los vecinos más activos en 00:31:58.900 --> 00:32:00.166 Búsqueda de adyacencia máxima. 00:32:00.800 --> 00:32:04.000 Vas a ser un poco más indulgente. 00:32:04.000 --> 00:32:05.766 con esta activación y vas a activar 00:32:05.766 --> 00:32:07.900 cualquier nodo inactivo que tenga al menos kappa 00:32:07.900 --> 00:32:09.000 vecinos activos. 00:32:11.466 --> 00:32:13.900 Estas reglas son solo dos reglas diferentes para 00:32:13.900 --> 00:32:14.800 Haz lo mismo, ¿verdad? 00:32:14.833 --> 00:32:18.066 Como si ambos fueran privilegiados, estos pares de saltos múltiples 00:32:18.066 --> 00:32:21.800 que están respaldadas por rutas cortas redundantes, que 00:32:21.800 --> 00:32:23.966 es esta estructura mesoscópica que estamos tratando de 00:32:24.366 --> 00:32:25.400 para extraer. 00:32:25.833 --> 00:32:29.600 Y aquí solo tengo dos videos. 00:32:29.600 --> 00:32:36.500 mostrando cascada de umbral con dos parámetros kappa. 00:32:37.700 --> 00:32:40.100 Así que aquí, es un poco rápido, pero tú 00:32:40.100 --> 00:32:41.833 Como puedes ver, lo inicializo a cero. 00:32:42.400 --> 00:32:44.900 También tomo muestras de los nodos cuatro y tres y 00:32:44.900 --> 00:32:47.300 Entonces empiezo a mirar estos elementos lo más adyacentes posible. 00:32:47.300 --> 00:32:50.066 nodos adyacentes a cero, cuatro y tres y 00:32:50.066 --> 00:32:51.800 Hago esto repetidamente durante un cierto número 00:32:51.800 --> 00:32:52.333 de pasos. 00:32:53.033 --> 00:32:55.500 Esto es para umbrales pequeños que terminan 00:32:55.500 --> 00:32:57.366 activando muchos nodos al final. 00:32:57.566 --> 00:32:59.333 Así que terminan activando 10 de cada 00:32:59.333 --> 00:33:00.066 60 nodos. 00:33:00.666 --> 00:33:02.500 Aquí, si aumentas un poco el umbral 00:33:02.500 --> 00:33:05.300 un poco, las activaciones son más raras. 00:33:05.700 --> 00:33:08.666 Naturalmente, estás activando, eventualmente estás activando el uno 00:33:08.666 --> 00:33:09.100 -vecinos saltando. 00:33:10.666 --> 00:33:12.400 Así que no te vas a deshacer de este local 00:33:12.400 --> 00:33:15.000 estructura, pero hay cierta selectividad en cómo lo haces 00:33:15.000 --> 00:33:17.966 ¿Activando a tus vecinos de salto más lejanos, verdad? 00:33:17.966 --> 00:33:19.766 Tus vecinos de dos saltos, tres saltos y así sucesivamente 00:33:19.766 --> 00:33:19.933 en. 00:33:20.766 --> 00:33:24.266 Por lo tanto, esta selectividad se basa en este máximo. 00:33:24.266 --> 00:33:25.700 idea de adyacencia. 00:33:25.700 --> 00:33:30.733 Y también estos gráficos auxiliares, no son tan... 00:33:30.733 --> 00:33:32.600 No es muy caro de construir, ¿verdad? 00:33:32.633 --> 00:33:36.433 Como si, si m es de orden n, 00:33:36.500 --> 00:33:37.933 Esto va a ser O de n 00:33:37.933 --> 00:33:39.000 construir. 00:33:39.400 --> 00:33:40.933 Y entonces la idea es tomar estos 00:33:40.933 --> 00:33:43.300 gráficos auxiliares y los pasa como la columna vertebral 00:33:45.133 --> 00:33:47.633 a una GNN o a un transformador de gráficos. 00:33:50.033 --> 00:33:53.833 Así que tenemos un par de resultados teóricos. 00:33:53.833 --> 00:33:56.533 para respaldar de alguna manera este enfoque. 00:33:57.333 --> 00:34:01.033 Una de ellas demuestra que la reconfiguración ayuda cuando... 00:34:01.033 --> 00:34:03.266 tienen gráficos que son heterofílicos. 00:34:04.233 --> 00:34:08.766 Entonces, aquí, supongamos que tenemos que 00:34:08.766 --> 00:34:10.333 ¿Puedo escribir tres eventos, verdad? 00:34:10.366 --> 00:34:13.066 Entonces, el primero son los acuerdos de etiquetas, lo que significa 00:34:13.066 --> 00:34:15.200 Los nodos tienen la misma etiqueta en cualquier tarea. 00:34:15.200 --> 00:34:16.466 estás tratando de resolver. 00:34:19.533 --> 00:34:22.366 Esta será una L caligráfica, evento L caligráfico. 00:34:23.300 --> 00:34:25.733 El evento caligráfico E será que hay un 00:34:25.733 --> 00:34:27.733 borde, no un borde dirigido, solo un borde 00:34:27.733 --> 00:34:30.333 entre los nodos U y V, lo que significa que son adyacentes 00:34:30.333 --> 00:34:31.033 en el gráfico. 00:34:31.666 --> 00:34:33.600 Y la R caligráfica significará que tienes 00:34:33.600 --> 00:34:38.766 refuerzo, lo que significa que hay al menos kappa co 00:34:38.766 --> 00:34:41.066 -ocurrencias de U y V en. 00:34:41.633 --> 00:34:46.166 Entonces, dados estos eventos y dado un aleatorio 00:34:46.166 --> 00:34:49.233 par no ordenado de nodos distintos U, V, nosotros 00:34:49.233 --> 00:34:52.300 define la homofilia de arista estándar como la probabilidad 00:34:52.300 --> 00:34:55.200 que usted tiene un acuerdo de etiqueta dado que usted 00:34:55.200 --> 00:34:57.800 tienen una ventaja entre U y V, y 00:34:57.800 --> 00:35:00.566 la homofilia de refuerzo o la homofilia en la 00:35:00.566 --> 00:35:03.733 gráfico reconectado como la probabilidad de que tengas 00:35:03.733 --> 00:35:06.766 acuerdo de etiqueta dado que tiene refuerzo, o 00:35:06.766 --> 00:35:08.466 en otras palabras, dado que tienes adyacencia 00:35:08.466 --> 00:35:09.500 en el gráfico reconectado. 00:35:10.933 --> 00:35:12.700 Y entonces lo que estábamos preguntando aquí era, 00:35:12.966 --> 00:35:15.933 ¿Cuándo se presenta esta homofilia en el gráfico reconfigurado? 00:35:15.933 --> 00:35:18.666 ¿Mayor que la homofilia en el gráfico original? 00:35:18.966 --> 00:35:20.633 La razón de esto es porque sabemos 00:35:20.633 --> 00:35:23.433 que las convoluciones gráficas de GNN funcionan bien cuando 00:35:23.433 --> 00:35:24.300 ¿Tienen homofilia, verdad? 00:35:24.333 --> 00:35:27.866 Entonces, cuando nodos similares, nodos no similares, nodos 00:35:27.866 --> 00:35:31.166 que están conectados en el gráfico tienen similares 00:35:32.166 --> 00:35:35.233 vecinos, etiquetas similares o, por ejemplo, señales. 00:35:35.633 --> 00:35:38.166 Esto es lo que mide la energía de Dirichlet, ¿verdad? 00:35:38.166 --> 00:35:42.133 Más en nuestra conversación, más en procesamiento de señales 00:35:42.133 --> 00:35:42.533 términos. 00:35:43.533 --> 00:35:46.833 Entonces, lo que mostramos en esta proposición aquí 00:35:46.833 --> 00:35:48.033 es que bajo dos condiciones. 00:35:48.033 --> 00:35:51.533 Entonces, bajo la condición de que tengamos un orden 00:35:51.533 --> 00:35:56.033 de heterofilia en G, lo que significa que siempre que la 00:35:56.033 --> 00:35:58.033 Las etiquetas entre dos nodos U y V coinciden, 00:35:58.533 --> 00:36:00.766 tienes una mayor probabilidad de que sean 00:36:00.766 --> 00:36:03.700 en la ruta de múltiples saltos en comparación con que sean 00:36:03.700 --> 00:36:05.233 vecinos directos. 00:36:05.933 --> 00:36:08.566 Y cuando el evento de refuerzo es menos frecuente 00:36:08.566 --> 00:36:12.600 que los bordes, entonces la homofilia de ese cableado reconectado 00:36:12.600 --> 00:36:14.733 El gráfico es mayor que la homofilia de la 00:36:14.733 --> 00:36:15.433 gráfico original. 00:36:16.033 --> 00:36:17.833 Y esto es mayor o igual que, pero 00:36:17.833 --> 00:36:20.233 Será estricto cuando se den estas condiciones. 00:36:20.233 --> 00:36:20.766 estricto. 00:36:21.733 --> 00:36:26.066 Y aquí intentamos ilustrar esto con 00:36:26.066 --> 00:36:28.133 Algunos gráficos sintéticos y reales. 00:36:28.600 --> 00:36:30.966 Entonces lo que hicimos fue que nosotros, la homofilia 00:36:30.966 --> 00:36:34.533 antes y después del recableado, en comparación con el registro de 00:36:34.533 --> 00:36:39.066 el grado promedio original y los tamaños de 00:36:39.066 --> 00:36:41.400 Las bolas aquí indican la homofilia. 00:36:41.633 --> 00:36:45.166 Los puntos tan pequeños, como estos, tienen una baja homofilia. 00:36:45.366 --> 00:36:47.500 Los círculos más grandes presentan una alta homofilia. 00:36:48.333 --> 00:36:49.366 Y entonces lo que ves es que nosotros 00:36:49.366 --> 00:36:53.166 obtener el mayor aumento de homofilia justo aquí 00:36:53.166 --> 00:36:58.166 aquí cuando los gráficos originales son heterofílicos y 00:36:58.166 --> 00:37:00.933 cuando tienen un título universitario alto, ¿verdad? 00:37:01.600 --> 00:37:05.433 En algunos casos, la homofilia empeora, como 00:37:05.433 --> 00:37:08.266 especialmente para grafos de bajo grado muy homofílicos. 00:37:12.266 --> 00:37:15.000 Bien, y luego los otros resultados que tenemos 00:37:15.000 --> 00:37:16.800 lo tenemos, y este es un resultado muy simple, 00:37:16.833 --> 00:37:19.333 Está muy relacionado con lo que Antonio comentó sobre 00:37:19.333 --> 00:37:24.900 Lunes, la resistencia efectiva de los bordes en 00:37:24.900 --> 00:37:28.133 ¿El gráfico reconectado, verdad? 00:37:28.233 --> 00:37:30.500 Entonces, básicamente, quiero decir, lo que estamos capturando una vez 00:37:30.500 --> 00:37:34.433 Realizamos esta reconfiguración neuronal basándonos en la coactivación. 00:37:34.666 --> 00:37:38.100 correcto, o nodos que aparecen en múltiples saltos múltiples 00:37:38.100 --> 00:37:42.100 rutas, es que estamos codificando redundancia estructural, ¿verdad?, en 00:37:42.100 --> 00:37:42.500 el gráfico. 00:37:43.366 --> 00:37:48.633 Y básicamente lo que esa redundancia estructural significa formalmente. 00:37:48.633 --> 00:37:51.133 Si es eso, entonces lo que eso significa es que 00:37:51.133 --> 00:37:54.733 G tiene K caminos cortos disjuntos por pares de aristas. 00:37:54.733 --> 00:37:57.100 desde la semilla hasta ti, ¿verdad? 00:37:57.233 --> 00:38:03.433 Y esto limita directamente la resistencia efectiva I 00:38:03.433 --> 00:38:07.833 probablemente no sea necesario volver a definir esto después 00:38:07.833 --> 00:38:12.233 La charla de Antonio, pero básicamente se trata solo de medir el tipo 00:38:12.233 --> 00:38:18.166 como la diferencia de voltaje entre dos nodos, 00:38:18.400 --> 00:38:20.466 correcto, basado en la pseudoinversa de la 00:38:20.466 --> 00:38:22.500 Laplaciano aquí, si crees que tienes 00:38:22.500 --> 00:38:24.933 una fuente actual en U y una actual 00:38:24.933 --> 00:38:25.966 fregadero en V. 00:38:26.933 --> 00:38:28.800 Y el límite superior que obtenemos para 00:38:28.800 --> 00:38:32.966 esta resistencia efectiva en estos bordes recableados es 00:38:32.966 --> 00:38:36.733 dada por L, que es la longitud de 00:38:36.733 --> 00:38:40.333 el kappa, donde kappa es el umbral de activación. 00:38:41.533 --> 00:38:45.200 Bien, entonces esencialmente aquí, no es que estemos 00:38:45.200 --> 00:38:48.333 no estamos preservando los cuellos de botella, ¿verdad?, porque los cuellos de botella son 00:38:48.333 --> 00:38:53.833 nodos con, son bordes con alta resistencia efectiva. 00:38:54.133 --> 00:38:59.200 Estamos preservando estos redundantes, por lo que estos pares que 00:38:59.200 --> 00:39:02.000 corresponder a redundante, a redundancia en el gráfico. 00:39:02.300 --> 00:39:06.433 Estamos preservando, estamos conectando nodos con baja efectividad 00:39:06.433 --> 00:39:07.566 resistencia. 00:39:09.666 --> 00:39:13.833 Bien, entonces solo unos pocos resultados numéricos antes 00:39:13.833 --> 00:39:14.533 Concluyo. 00:39:15.466 --> 00:39:17.566 Entonces, y lo que vimos fue, primero de 00:39:17.566 --> 00:39:19.000 En general, funciona bastante bien. 00:39:19.233 --> 00:39:24.733 Entonces, en algunos conjuntos de datos, logra, 00:39:24.933 --> 00:39:25.733 como, la mejor actuación. 00:39:25.966 --> 00:39:28.866 En otros casos, lo hace comparativamente con el uso del 00:39:28.866 --> 00:39:31.433 gráfico original, que es, que es bonito. 00:39:31.600 --> 00:39:33.866 Pero tal vez lo más interesante sea el 00:39:33.866 --> 00:39:34.900 alineación con la teoría. 00:39:35.033 --> 00:39:36.733 Así que vemos que las mayores ganancias 00:39:36.733 --> 00:39:42.266 ocurren para gráficos heterofílicos con un alto grado. 00:39:42.733 --> 00:39:45.900 Cuando los supuestos de ese primer teorema sobre 00:39:45.900 --> 00:39:48.266 la, sobre la homofilia mejorada de la, de 00:39:48.266 --> 00:39:52.033 Si el gráfico reconfigurado no se sostiene, entonces no lo hicimos. 00:39:52.033 --> 00:39:53.666 Se observan muchas ganancias. 00:39:53.866 --> 00:39:55.633 Así que esto parece ser más útil. 00:39:55.633 --> 00:39:56.833 para gráficos heterofílicos. 00:39:57.366 --> 00:40:00.533 Aunque agnósticos, esto es solo GCN, ¿verdad? 00:40:00.533 --> 00:40:04.300 y estas son tres arquitecturas diferentes de transformadores de gráficos. 00:40:04.833 --> 00:40:06.266 Todos estos son una especie de grafo disperso. 00:40:06.266 --> 00:40:09.533 transformadores donde no tienes la estructura del gráfico, 00:40:09.666 --> 00:40:13.766 pero de alguna manera les das a los vecinos incrustaciones 00:40:13.766 --> 00:40:14.633 como fichas. 00:40:15.333 --> 00:40:17.033 Así que puedes usar este gráfico reconfigurado. 00:40:17.033 --> 00:40:17.233 allá. 00:40:17.333 --> 00:40:19.400 En estos dos casos, hemos tenido una mejora bastante notable. 00:40:20.366 --> 00:40:23.900 Y aquí, hay más detalles sobre 00:40:23.900 --> 00:40:25.733 la mejora que obtuvimos en estos heterofílicos 00:40:25.733 --> 00:40:26.466 conjuntos de datos, ¿verdad? 00:40:26.466 --> 00:40:29.300 Así que, especialmente para Chameleon y Cornell, las mejoras 00:40:29.300 --> 00:40:31.433 eran, eran bastante buenos. 00:40:33.533 --> 00:40:36.866 Otra de las mejores precisiones que obtuvimos en estos 00:40:36.866 --> 00:40:40.966 gráficos reconectados, en la etiqueta homofilia, el logaritmo 00:40:40.966 --> 00:40:44.933 grado promedio y la conectividad de la, de 00:40:44.933 --> 00:40:47.766 tanto el gráfico original como el recableado. 00:40:49.066 --> 00:40:51.466 Y lo que vimos es que, entonces M 00:40:51.466 --> 00:40:52.766 -ASTAS aquí están nuestros 00:40:52.766 --> 00:40:53.366 métodos, ¿verdad? 00:40:53.833 --> 00:40:55.433 Entonces los valores de beta aquí, pero 00:40:55.433 --> 00:40:57.866 especialmente centrándonos en el R cuadrado, el ajustado 00:40:57.866 --> 00:41:01.533 R cuadrado aquí, ya que, como puede ver, el 00:41:02.200 --> 00:41:05.900 diferencia en, en, o la precisión de la prueba, la 00:41:05.900 --> 00:41:09.266 Las mejoras en la precisión de las pruebas se explican mucho mejor. 00:41:10.766 --> 00:41:14.133 por las propiedades estructurales de este grafo reconfigurado 00:41:14.133 --> 00:41:15.666 En el gráfico original, ¿verdad? 00:41:15.733 --> 00:41:18.433 Entonces hay mejoras en la homofilia y esto 00:41:18.433 --> 00:41:22.666 cambio en la resistencia efectiva en el gráfico recableado 00:41:22.666 --> 00:41:24.766 Parece que sí ayudan al rendimiento. 00:41:25.633 --> 00:41:31.966 Bueno, para concluir, hoy hablé 00:41:31.966 --> 00:41:37.266 sobre el intento de preservar la topología mesoscópica y global 00:41:37.266 --> 00:41:38.866 en, en gráficos. 00:41:40.100 --> 00:41:43.533 Para aproximar las distancias globales, vimos ese hito. 00:41:43.533 --> 00:41:46.866 Las incrustaciones son un buen método, ¿verdad? 00:41:46.966 --> 00:41:49.000 Eso todavía tiene ese paso local, 00:41:49.166 --> 00:41:51.533 pero luego lo aumenta con un, con un 00:41:51.533 --> 00:41:52.200 paso global. 00:41:52.966 --> 00:41:56.066 Y aunque la distorsión garantiza que estos 00:41:56.066 --> 00:41:58.466 Los algoritmos son bastante malos en el peor de los casos, 00:41:58.933 --> 00:42:01.333 vemos que en los gráficos de casos más promedio, 00:42:01.433 --> 00:42:02.233 La distorsión es. 00:42:02.466 --> 00:42:05.100 También vimos que existe una dependencia interesante. 00:42:05.100 --> 00:42:10.466 sobre la dimensión de incrustación en el Peronico, y 00:42:10.466 --> 00:42:12.666 que podemos reemplazar esa búsqueda en amplitud 00:42:12.666 --> 00:42:16.033 entrar, en el paso local con un 00:42:16.033 --> 00:42:20.366 GNN sustituto que luego nos permite ordenar 00:42:20.366 --> 00:42:22.533 de aprovechar las buenas propiedades de GNN tales 00:42:22.533 --> 00:42:23.766 como, como transferibilidad. 00:42:25.066 --> 00:42:27.533 Y luego en la segunda parte, hablando de 00:42:28.766 --> 00:42:32.833 Para incrustar o preservar la estructura mesoscópica, utilizamos gráficos. 00:42:32.833 --> 00:42:33.633 cascadas. 00:42:33.633 --> 00:42:38.066 En estas escalas mesoscópicas globales, convoluciones y atención 00:42:38.066 --> 00:42:40.766 puede ser insuficiente, ¿verdad? 00:42:40.933 --> 00:42:43.666 Entonces, una posible, quiero decir, hay muchas 00:42:43.666 --> 00:42:47.300 enfoques a estas estructuras, correcto, para obtener incrustaciones 00:42:47.300 --> 00:42:49.766 que incorporan estas estructuras. 00:42:51.066 --> 00:42:53.366 Pero el enfoque que adoptamos aquí, y 00:42:53.366 --> 00:42:55.933 el enfoque que yo, yo, yo creo que es, 00:42:56.566 --> 00:42:59.566 ya sabes, sostengo que es un buen enfoque, 00:42:59.766 --> 00:43:02.400 es hacer uso del apropiado 00:43:02.400 --> 00:43:04.666 métrica, correcto, para intentar preservar lo apropiado 00:43:04.666 --> 00:43:05.033 métrico. 00:43:05.166 --> 00:43:07.033 Así pues, a escala global, el camino más corto 00:43:07.033 --> 00:43:09.533 métrica, en la escala local, en la escala mesoscópica, 00:43:10.033 --> 00:43:14.366 cosas como resistencia efectiva, redundancia y aquí estamos 00:43:14.366 --> 00:43:16.000 Intenta hacerlo de dos maneras. 00:43:16.233 --> 00:43:19.633 Entonces, primero, dentro del modelo ML, ¿verdad?, entonces 00:43:20.700 --> 00:43:25.500 tratando de aprender incrustaciones que, y en el 00:43:26.066 --> 00:43:28.666 Al tratar de preservar la escala mesoscópica, lo hicimos 00:43:28.666 --> 00:43:31.433 por lo tanto fuera del modelo ML a través de la reconfiguración, 00:43:31.733 --> 00:43:36.033 Correcto, y las infraestructuras troncales de ML y SP existentes. 00:43:36.933 --> 00:43:39.800 Ahora, en cuanto a la dirección futura, en relación con lo que 00:43:39.800 --> 00:43:41.533 Sergio preguntó, una cosa que podemos hacer 00:43:41.533 --> 00:43:42.966 ¿Podemos hacer una mejor semilla o hito? 00:43:42.966 --> 00:43:43.833 selección, ¿verdad? 00:43:43.866 --> 00:43:46.566 Por lo general, esto se hace de forma uniforme y aleatoria. 00:43:47.533 --> 00:43:50.266 Nuestros resultados dependen de ello, pero en la práctica usted 00:43:50.266 --> 00:43:54.733 podría hacerlo mejor usando el grado o la centralidad, 00:43:55.266 --> 00:43:59.300 incluso utilice la estructura en cascada en estos aleatorios 00:43:59.300 --> 00:44:01.466 paseos para seleccionar los lugares de interés. 00:44:01.966 --> 00:44:05.666 Otra dirección que estamos siguiendo es la de extender esas 00:44:05.666 --> 00:44:09.533 garantías de distorsión de incrustación de ruta más corta para grafos dirigidos, 00:44:10.466 --> 00:44:12.833 lo cual es un poco más desafiante porque 00:44:12.833 --> 00:44:14.600 Ahora su matriz D no es simétrica y 00:44:14.600 --> 00:44:16.766 tienes que asegurarte de que estás respetando el 00:44:16.766 --> 00:44:18.266 orientaciones de los bordes individuales. 00:44:20.766 --> 00:44:25.700 También podría hacerse alguna señal o función sensible 00:44:25.700 --> 00:44:27.133 Selección en cascada, ¿verdad? 00:44:27.166 --> 00:44:29.833 Así que ignoramos por completo las características del nodo cuando 00:44:29.833 --> 00:44:32.666 estamos haciendo la selección en cascada o cuando 00:44:32.666 --> 00:44:35.966 estamos calculando esos nodos adyacentes máximos 00:44:35.966 --> 00:44:36.266 pares. 00:44:36.666 --> 00:44:40.366 Y finalmente, porque realmente nos estamos centrando en 00:44:40.366 --> 00:44:44.233 este método de recableado en nodos que tienen algunos 00:44:44.233 --> 00:44:48.633 redundancia estructural a escala mesoscópica, el método 00:44:48.633 --> 00:44:51.866 termina por no funcionar bien para gráficos donde 00:44:51.866 --> 00:44:54.866 tienes cuellos de botella o problemas donde el 00:44:54.866 --> 00:44:55.866 Los cuellos de botella son importantes. 00:44:56.133 --> 00:45:00.933 Así que tal vez combinar este método de recableado con algunos 00:45:00.933 --> 00:45:05.400 La reestructuración dirigida a los cuellos de botella podría darnos mejores resultados. 00:45:05.400 --> 00:45:09.500 a escala mesoscópica y nos permite 00:45:09.500 --> 00:45:11.366 cruzar cortes más estrechos. 00:45:13.266 --> 00:45:16.466 Gracias, entonces estos son los dos documentos. 00:45:16.466 --> 00:45:20.333 y gracias a mis colaboradores. 00:45:25.933 --> 00:45:27.433 Gracias. 00:45:29.333 --> 00:45:31.233 Johanna, gracias por la presentación. 00:45:32.033 --> 00:45:33.266 Disculpen si me lo perdí. 00:45:33.400 --> 00:45:36.633 Tengo curiosidad por los resultados, dado que 00:45:36.633 --> 00:45:41.366 Se dice que los transformadores de gráficos son naturalmente mejores para los heterofílicos. 00:45:41.366 --> 00:45:46.833 tareas, ya sea que esta mejora independiente del modelo ponga 00:45:46.833 --> 00:45:49.866 Las GNN están a la par para observar una diferencia. 00:45:50.566 --> 00:45:51.900 Sí, no creo que tenga la materia prima. 00:45:51.900 --> 00:45:54.400 En términos numéricos, pero en la práctica los transformadores estaban funcionando mejor. 00:45:54.633 --> 00:45:56.500 Sí, casi siempre. 00:45:56.766 --> 00:45:58.766 Además, creo que solo probamos GCN. 00:45:58.900 --> 00:46:00.366 GCN no es muy bueno para esto. 00:46:00.733 --> 00:46:02.933 Sí, eso también podría ser un artefacto. 00:46:03.466 --> 00:46:03.766 Veo. 00:46:04.066 --> 00:46:04.500 Gracias. 00:46:07.733 --> 00:46:09.933 Yo también tengo una pregunta sobre la primera parte. 00:46:13.633 --> 00:46:17.266 Por lo general, estas redes reales siempre tienen una carencia. 00:46:17.266 --> 00:46:17.666 bordes. 00:46:17.666 --> 00:46:20.966 Afectan a la búsqueda de la ruta más corta, etc. 00:46:21.733 --> 00:46:24.466 Lo que la gente a veces hace, todavía los incorporan. 00:46:24.466 --> 00:46:27.000 en un espacio hiperbólico o cualquier otro espacio 00:46:27.000 --> 00:46:28.833 y tratar de averiguar allí cómo 00:46:28.833 --> 00:46:29.766 encontrar los caminos más cortos. 00:46:31.400 --> 00:46:33.866 ¿Crees que ahora es posible extenderlo? 00:46:33.866 --> 00:46:34.033 ¿él? 00:46:36.166 --> 00:46:38.066 Respuesta a ¿existe un camino más corto entre? 00:46:38.066 --> 00:46:40.266 dos nodos desconectados no, no los hay. 00:46:40.366 --> 00:46:42.766 O como el camino más corto tiene, el más corto 00:46:42.766 --> 00:46:43.666 La distancia es infinita. 00:46:44.366 --> 00:46:49.766 Bien, entonces asumimos o porque, entonces 00:46:49.766 --> 00:46:51.933 cuando hacemos esta aproximación del proceso de ramificación, 00:46:51.933 --> 00:46:54.366 supongamos que estamos en el régimen supercrítico y 00:46:54.366 --> 00:46:56.366 Allí, con alta probabilidad, tienes uno gigante. 00:46:56.366 --> 00:46:57.266 componente conectado. 00:46:57.733 --> 00:46:59.133 Así que aprovechamos eso, ¿verdad? 00:47:01.733 --> 00:47:03.133 Es importante, sí. 00:47:10.466 --> 00:47:13.233 Hablaste de recablear allí como una manera 00:47:13.233 --> 00:47:14.966 para mitigar esto e investigar. 00:47:15.566 --> 00:47:18.800 La gente también analiza en detalle los nodos virtuales. 00:47:18.800 --> 00:47:21.100 Lo cual sería en lugar de simplemente recablear en 00:47:21.100 --> 00:47:22.900 de los nodos existentes, tienes un nodo adicional 00:47:22.900 --> 00:47:24.833 y luego puedes hacer ambos recableados o 00:47:24.833 --> 00:47:25.600 nuevos bordes con eso. 00:47:26.466 --> 00:47:27.966 Y tengo la sensación de que lo hará. 00:47:27.966 --> 00:47:30.633 Realmente ayudan en algunos de estos aspectos. 00:47:32.400 --> 00:47:35.533 Sí, entonces, si no me equivoco, esto 00:47:35.533 --> 00:47:37.333 VCR uno, creo que la V significa 00:47:37.333 --> 00:47:37.600 virtual. 00:47:37.733 --> 00:47:40.133 Entonces creo que es uno de los gráficos 00:47:40.133 --> 00:47:42.066 transformadores que tienen esta ventaja virtual. 00:47:42.500 --> 00:47:44.000 Entonces quiero decir que mantenemos la ventaja virtual, 00:47:44.100 --> 00:47:46.733 pero solo añadimos este recableado, ¿verdad? 00:47:46.933 --> 00:47:49.733 Y aún se aprecian algunas mejoras importantes. 00:47:49.933 --> 00:47:53.000 Así que supongo que sí, ayuda. 00:47:53.000 --> 00:47:54.233 Porque el nodo virtual, si lo piensas 00:47:54.233 --> 00:47:55.866 es como agregar este global 00:47:55.866 --> 00:47:57.900 Es como un nodo que conecta a todo el mundo, ¿verdad? 00:48:00.633 --> 00:48:02.600 Eso es cierto, eso es cierto, sí.